\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
%\usepackage[french,boxed]{algorithm2e}
%\usepackage{fullpage}
\usepackage{xkeyval}
\usepackage{amsmath}
\usepackage{amsfonts,amssymb}
\usepackage{float}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{listings}
\usepackage{multicol}
\usepackage{pstricks}
\usepackage{aeguill}
\usepackage{color}
\usepackage{mathenv}
%\usepackage{a4}
\usepackage{graphicx}
\usepackage{color}

\definecolor{jbackground}{rgb}{0.9,0.9,0.9}
\lstset{language=C, backgroundcolor=\color{jbackground}}


\addtolength{\hoffset}{-1cm} %////////////////////////
\addtolength{\textwidth}{1cm} 
\setlength{\headsep}{0.70cm}
%%%%%%%%%%%%% Java Listings %%%%%%%%%%%%%
\definecolor{jbackground}{rgb}{0.75,0.75,0.75}
%\lstset{language=C, backgroundcolor=\color{jbackground}}

%%%%%%%%%%%%%%%% Variables %%%%%%%%%%%%%%%%
\def\titre{Bibliothèque de Gestion de Threads}
\def\titregauche{Projet S8}
\def\titredroite{Compte-rendu du Projet Système}
\def\filiere{informatique}
\def\annee{$2^{\`eme}$}  % $1^{ere}$, $2^{eme}$ ou $3^{eme}$
\def\anneescolaire{2011/2012}
\def\numeroequipe{}
\def\equipe{Mohamed Ayoub GHARSSALLI\\Abdessamad HAILASS\\Meryem KESMI\\Bastien STEFANI\\Charaf-Eddine SHITIT}
\def\encadrant{Damien MARTIN-GUILLEREZ} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\pagestyle{fancy} \lhead{\textsc{\titregauche}} 
\rfoot{\textit{Ann\'ee \anneescolaire}}\rhead{\textsc{\titredroite}}\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}

\begin{document}

\begin{titlepage}

\begin{center}


% Upper part of the page
\begin{center}
\rotatebox{0}{\scalebox{1}[1]{\includegraphics[width=6cm]{logo.jpg}}}
\end{center}
~\\
~\\
~\\
\textsc{\LARGE ENSEIRB-MATMECA}\\[1cm]

\textsc{\Large {Fili\`ere \filiere, \annee ann\'ee}}\\[0.5cm]

% Title
\HRule \\[0.4cm]
{ \huge \bfseries \titre}\\[0.4cm]

\HRule \\[1.5cm]

% Author and supervisor
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\emph{Auteurs:}\\
\equipe
\end{flushleft}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
\emph{Encadrant:} \\
\encadrant
\end{flushright}
\end{minipage}

\vfill

% Bottom of the page
%{\large \today}

\end{center}

\end{titlepage}

\tableofcontents{}
\newpage
%%%%%%%%%%%%%%%% Main part %%%%%%%%%%
\section{introduction}
  Le projet de système d'exploitation consiste à réaliser une bibliothèque de threads en espace utilisateur à l'aide du langage \textbf{C}. Pour réaliser notre bibliothèque, nous avons utilisé l'interface de programmation \texttt{ucontext} qui permet de manipuler des contextes de threads et ce  en espace utilisateur. Cette bibliothèque de threads doit satisfaire les critères suivants :
\begin{itemize}
\item Les coûts d'ordonnancement sont beaucoup plus faibles
\item Les politiques d'ordonnancement sont configurables
\item Pouvoir expérimenter réellement le changement de contexte
\end{itemize}
Dans ce rapport, nous allons commencer par la description du travail réalisé: le choix des structures mises en place, ensuite nous allons nous intéresser à l'implémentation de l'interface de gestion de threads ainsi que les certains objectifs avancés qui ont été atteints. Enfin nous allons présenter des tests qui montrent la validité du comportement de notre bibliothèque de gestion de threads.

\section{Travail accompli}
Dans cette partie, nous allons présenter et expliquer les structures réalisées nécessaires à la construction de la bibliothèque de gestion de threads. Ensuite, nous allons nous intéresser à l'implémentation de cette interface de threads qui permet de créer, détruire, passer la main (éventuellement à un thread particulier), attendre la/une terminaison ... etc.


\subsection{La structure des threads}

Pour représenter un thread en mémoire, nous avons défini la structure suivante : 
\begin{lstlisting}
struct thread {
   thread_status status;
   ucontext_t context;
   struct timeval * execution_time;
   void * retval;
};
\end{lstlisting}

Cette structure regroupe les champs : 
\begin{itemize}
\item \textbf{status} : le status d'un thread. Nous avons utilisé une énumération des états d'un thread (ENDED, SLEEPING,RUNNING)
\item \textbf{context} : le contexte d'exécution du thread
\item \textbf{execution\_time} : le temps d'exécution d'un thread afin de gérer la préemption
\item \textbf{retval} : la valeur de retour d'un thread (accessible uniquement une fois que le thread a fini de s'exécuter)
\end{itemize}


\subsection{La structure d'organisation des threads}
Nos threads seront stockés sur 3 structure appelée \textbf{runq}, \textbf{sleepq} et \textbf{deadq}. Ces structure étaient dans un premier temps implémentées grâce à une file FIFO. Ensuite dans un soucis de performance d'insertion et de recherche nous avons opté pour une liste doublement chainée. Ce TAD est actuellement en modification en vue de le rendre circulaire. Ceci permettra d'accélérer le passage d'un thread à un autre.

\subsubsection{La runq}

Elle rassemble tout les threads créés et prêts à s'exécuter. A chaque changement de contexte d'exécution, le thread courant est mis dans cette liste et est remplacé par le suivant dans cette liste, en tant que thread courant. La valeur de \verb$thread_status$ (variable de la structure \verb$thread$) est \verb$RUNNING$ pour tous les threads de cette liste. Cette liste contiendra donc aussi le main qui est le premier à y être ajouté.

\subsubsection{La sleepq}


La seconde liste est la \verb$sleepq$, celle-ci stockera les threads bloqués par un appel système bloquant ou à la demande de l'utilisateur et propriétaire des threads. Actuellement, nous n'utilisont pas encore cette liste, mais l'avons déjà implémentée pour pouvoir étendre les possibilitées de notre librairie.
La valeur de \verb$thread_status$ (variable de la structure \verb$thread$) est \verb$SLEEPING$ pour tous les threads qui seront dans cette liste.

\subsubsection{La deadq}

Elle contient les valeurs de retour des threads ayant fini leur exécution. Elle est consultée par les thread qui voudront récupérer ces valeurs. Nous avons fait le choix que ce thread videra l'entrée correspondante à celui qu'il attend. La valeur de \verb$thread_status$ (variable de la structure \verb$thread$) est \verb$ENDED$ pour tous les threads qui seront dans cette liste.

\subsection{Implémentation de l'interface de gestion de threads}

Afin de manipuler les différents threads de notre programme et donc manipuler la structure \verb$thread$ que nous avons créée, un ensemble de fonctions ont été implémentées.
\\
\\
\begin{lstlisting}
La fonction thread_init :
\end{lstlisting}
Pour commencer, la première fonction que nous avons dû implementer est la fonction d'initialisation d'un nouveau threads, le premier thread courant (généralement le \verb$main$) : \verb$thread_init$.
Cette fonction ne prend pas de paramètre, alloue la mémoire nécessaire au stockage du thread courant et initialise les variables de la structure \verb$thread$ créée. Cette fonction permet donc de gérer la fonction \verb$main$ comme un thread classique et de le placer dans la \verb$runq$.
\\
\\
\begin{lstlisting}
La fonction thread_self :
\end{lstlisting}
C'est un fonction qui permet de récuperer le thread courant. Pour cela, la fonction thread\_self retourne la variable globale \textbf{current} dans laquelle nous stockons le thread courant.
\\
\\
\begin{lstlisting}
La fonction thread_create :
\end{lstlisting}
La seconde fonction nécessaire à la création du thread est la fonction de création \verb$thread_create$.
\\
Cette fonction prend en paramètre 3 arguments : un pointeur sur le thread à créer, un pointeur de fonction pointant sur la fonction que devra appeler le thread et un pointeur sur l'argument de la fonction à exécuter. Notre fonction initialise la structure du thread à créer et son contexte grâce à la fonction makecontext(). Le thread est ensuite stocké dans la \verb$runq$. Un \verb$thread_yield$ est ensuite lancé (la fonction \verb$thread_yield$ sera expliquée plus loin) et la valeur de retour de la fonction lancée par le thread est stockée dans la variable \verb$retval$.
\\
\\
\begin{lstlisting}
La fonction thread_yield :
\end{lstlisting}
La fonction \verb$thread_yield$ citée plus haut est une fonction permettant de lancer l'exécution du thread suivant de la \verb$runq$.
\\
Dans cette fonction, le thread courant est placé à la fin de la \verb$runq$, un changement de contexte est effectué grâce à la fonction \verb$swapcontext$ afin de lancer le thread suivant.
\newpage
\begin{lstlisting}
La fonction thread_exit :
\end{lstlisting}
Une des dernières fonctions que nous avons implémentées est \verb$thread_exit$ qui permet de supprimer un thread qui est terminé.
\\
La fonction devant être appelée par un thread se termine par l'instruction \verb$thread_exit$ permettant de terminer le thread. Celui-ci est alors supprimé de la \verb$runq$ et placé dans la \verb$deadq$. La valeur de retour de la fonction est stockée dans la structure du thread afin d'être récupérée par la fonction \verb$thread_join$ (que nous verrons au paragraphe suivant).
\\
\\
\begin{lstlisting}
La fonction thread_join :
\end{lstlisting}
La dernière fonction, \verb$thread_join$ comme cité ci-dessus est une fonction permettant de récupérer la valeur de retour d'un thread mais aussi de maintenir un thread en attente grâce à un \verb$thread_yield$, ce qui n'est pas optimal pour le moment car le thread est rappelé tant que le thread passé en paramètre n'est pas terminé juste pour verifier son état et remis en fin de la \verb$runq$. L'espace mémoire occupé par le thread à détruire est à la fin de cette fonction libéré.
\\
\\
Un avantage de notre implémentation est que la valeur de retour de la fonction exécutée par un thread est accessible même si l'instruction \verb$thread_exit$ est omise car la fonction lancée par le thread est appelée par une fonction tampon (la fonction \verb$buffer_function$) stockant la valeur de retour de celle-ci.


\section{Options avancées}
\subsection{Intégration du main}

Le main a été dès le début considéré en tant qu'un thread ordinaire. Son ajout à la \textbf{runq} se fait grâce à la fonction \textbf{thread\_init()}. Nous gérons aussi le cas où \textbf{thread\_join} a pour destination le thread appelant.


\subsection{Ajout des fonctions de synchronisation de type sémaphores}
Pour implémenter les sémaphores, nous nous sommes basés sur la famille des standards POSIX. A chaque fois qu'un thread fait appel à \textbf{semaphore\_wait}, si le sémaphore n'est pas disponible  le thread rend la main, car celui-ci n'est pas bloqué pendant l'attente du sémaphore. En effet, il s'agit d'un attente active.
\subsection{Préemption}
La préemption fait partie des options prises en compte par notre bibliothèque. Comme suggéré par le sujet, il s'agit de garantir la bonne gestion des changements de contexte lors de l'interruption d'une tâche en faveur d'une autre par exemple. Ceci a été implémenté dans notre code en se basant sur les signaux de type \textbf{ITIMER\_VIRTUAL}. Une fonction \textbf{timer} permet de manipuler l'envoi de ces signaux , grâce à une valeur initiale fixée et une valeur d'intervalle au bout duquel le signal est envoyé. Une autre fonction \textbf{setitimer} lance le timer. Une fois le signal de préemption reçu, un appel à \textbf{thread\_yield} se fait, le contexte est donc changé et la main passé après interruption du code exécuté.


\section{Tests}
Afin de valider l'interface de gestion des threads mise en place ainsi que les options avancées implémentées, nous avons préparé des tests.
\subsection{Bon fonctionnement}

Nous avons utilisé nos fonctions sur l'exemple fourni \textbf{example.c}. L'exécution se
déroule correctement (l'exécutable est \textbf{my\_thread}).
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=0.8]{mythread.png}
\end{center}
\caption{Test de fonctionnement de l'exemple fourni } 
\end{figure}

\indent Nous avons vérifié avec Valgrind que les ressources mémoires allouées étaient bien libérées. Nous avons dû
ajouter les indications d'aide pour Valgrind (cf plus haut) avant d'être sûr que les libérations étaient effectives.
\newpage
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=0.8]{valgrind.png}
\end{center}
\caption{Vérification des fuites mémoire} 
\end{figure}

Nous avons implémenté une suite de Fibonacci utilisant les threads.
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=0.7]{fibo.png}
\end{center}
\caption{Exécution du test de Fibonacci} 
\end{figure}

\subsection{Performance}
Après avoir verifié le bon fonctionnement de notre bibliothèque de gestion des threads, nous allons nous intéresser aux performances de celle-ci. Ici, nous allons montrer à titre d'exemple le temps de calcul de \textbf{Fibo(27)}.
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=0.8]{fibo2.png}
\end{center}
\caption{Temps de calcul de Fibonacci(27)} 
\end{figure}


\section{Conclusion}
Pour conclure, ceci fut un projet très enrichissant puisqu’il s’agit de l'une de nos premières expériences dans un projet concret qui réunit plusieurs compétences notamment la programmation système et d'autres aspects de génie logiciel qui ont été partinents pour l'organisation au sein du groupe. Ce projet nous a permis de mettre en pratique ces différentes compétences souvent théoriques pour aboutir à cette application. Nous estimons que ce projet reste intéressant et formateur pour tous les membres de l'équipe.


\end{document}
 
